home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 297_01 / exampl8.spr < prev    next >
Text File  |  1980-01-01  |  3KB  |  144 lines
  1. /* example8.spr */
  2. /* list handling */
  3. /* lists are useful because they represent variable-size
  4.    sequences. Lists can even contain sublists.
  5.  */
  6. /* Most list handling algorithms are recursive.
  7.    To understand them you need to have a very precise
  8.    idea of how prolog's matching works. This is beyond
  9.    the scope of these comments. You could spend several
  10.    weeks trying to understand the C source code, but we
  11.    recommend you read a good book, bearing in mind
  12.    our notation is not Edinburgh prolog's (it's like
  13.    Micro-Prolog's)
  14.  
  15.    Suffice it to say that
  16.    the list (Head | Tail ) will match any list with at
  17.    least one element. The variable Head will match the
  18.    first element and Tail will match the sublist which 
  19.    is the rest.
  20.  
  21.    The file sprolog.ini is full of list handling
  22.    relations, some will be a bit obscure.
  23.   
  24.    Lots of examples are not harmful so here are some:
  25.    Most of the relations (or "predicates") are functions
  26.    in fact, so we take the convention that the result is
  27.    the value of the last argument :  
  28.    Many of these are so consise that it helps tracing 
  29.    to see how they work. But from the declarative point 
  30.    of view they are quite clear.
  31. */
  32.  
  33. /* self documenting */
  34. (list_has_exactly_3_elements (_ _ _))
  35.  
  36. /*************/
  37. ((display_elements (Head | Tail))
  38.  (display Head)
  39.  (nl)
  40.  (display_elements Tail)
  41. )
  42. (display_elements ())
  43.  
  44. /*************/
  45. (last_member (X) X)
  46. ((last_member (Head  | Tail) Last)
  47.  (last_member Tail Last)
  48. )
  49.  
  50. /*************/
  51.  
  52. (lists_have_same_length () ())
  53. ((lists_have_same_length (Head | Tail) (Head1 | Tail1) )
  54.  (lists_have_same_length Tail Tail1)
  55. )
  56.  
  57. ((middle_element L M)
  58.  (append L1 (M | L2) L)/* see sprolog.ini */
  59.  (lists_have_same_length L1 L2)
  60. ) /* This was a hard one : no call to a builtin was used */
  61.  
  62.  
  63. /*************/
  64.  
  65. (permute_list () ())
  66. ((permute_list (Head | Tail) Permuted)
  67.  (permute_list Tail Permuted_sublist)
  68.  (insert Head Permuted_sublist  Permuted)
  69. )
  70.  
  71. (insert X L (X | L))
  72. ((insert X (Head | Tail) (Head | Tail2))
  73.  (insert X Tail Tail2)
  74. )
  75.  
  76. /*************/
  77. ((reverse_list List Reversed)
  78.  (aux_reverse List () Reversed)
  79. )
  80.  
  81. ((aux_reverse (Head | Tail) Stack Reversed)
  82.  (aux_reverse Tail (Head | Stack) Reversed)
  83. )
  84. (aux_reverse () Reversed Reversed) 
  85.  
  86. /*************/
  87. ((set_union (Head | Tail ) List Union)
  88.  (member Head List)
  89.  (cut)
  90.  (set_union  Tail  List Union)
  91. )
  92. ((set_union (Head | Tail ) List (Head | Union))
  93.  (set_union  Tail  List Union)
  94. )
  95.  
  96. /*************/
  97.  
  98. ((minimum_of_list (Head| L) Min)
  99.  (minimum1 Head  L Min)
  100. )
  101.  
  102. ((minimum1 Min_found_so_far (H | T) Min)
  103.  (iless Min_found_so_far H)
  104.  (cut)
  105.  (minimum1 Min_found_so_far T Min)
  106. )
  107. ((minimum1 Min_found_so_far (H | T) Min)
  108.   (minimum1 H T Min)
  109. )
  110. (minimum1 Min () Min)
  111.  
  112.  
  113. /****************** demo section *****************/
  114. ((pause)(writes "Press return ")(get _))
  115.  
  116. (demo_list (aztec microsoft turbo watcom mw lattice metaware))
  117.  
  118. ((demo8)
  119.  (demo_list L)
  120.  (display_elements L)
  121.  (nl)
  122.  (pause)
  123.  (middle_element L M)
  124.  (display M)
  125.  (nl)
  126.  (pause) 
  127. /* warning : this going to be rather long */
  128.  (permute_list L Perm)
  129.  (display Perm)
  130.  (nl)
  131.  (fail) /* come here 7! times */
  132. )
  133. ((demo8) /* continues here */
  134.  (pause)
  135.  (demo_list L)
  136.  (reverse_list L R)
  137.  (display R)
  138.  (nl)
  139.  (pause)
  140.  (minimum_of_list (34 3 -9 7) Min)
  141.  (display Min)
  142.  (quit)
  143. )
  144.